#define _CRT_SECURE_NO_WARNINGS 1


//#include<iostream>
//
//using namespace std;
//
//struct ListNode 
//{
//	int val;
//	ListNode* next;
//	ListNode() 
//		:val(0)
//		,next(nullptr)
//	{ }
//	ListNode(int x) 
//		:val(x)
//		,next(nullptr) 
//	{ }
//	ListNode(int x, ListNode* next) 
//		:val(x)
//		,next(next) 
//	{ }
//};
//
//void _MergeSort(int* arr, int left, int right, int* temp)
//{
//	if (left >= right)
//	{
//		return;
//	}
//	int mid = (left + right) / 2;
//	_MergeSort(arr, left, mid, temp);
//	_MergeSort(arr, mid + 1, right, temp);
//	int begin1 = left, end1 = mid;
//	int begin2 = mid + 1, end2 = right;
//	int index = left;
//	while (begin1 <= end1 && begin2 <= end2)
//	{
//		if (arr[begin1] < arr[begin2])
//		{
//			temp[index++] = arr[begin1++];
//		}
//		else
//		{
//			temp[index++] = arr[begin2++];
//		}
//	}
//	while (begin1 <= end1)
//	{
//		temp[index++] = arr[begin1++];
//	}
//	while (begin2 <= end2)
//	{
//		temp[index++] = arr[begin2++];
//	}
//	for (int i = left; i <= right; i++)
//	{
//		arr[i] = temp[i];
//	}
//}
//
//void MergeSort(int* arr, int n)
//{
//	int* temp = new int[n];
//	_MergeSort(arr, 0, n - 1, temp);
//}
//
//int main()
//{
//	int arr[4] = { 4,2,1,3 };
//	MergeSort(arr, 4);
//	for (auto& e : arr)
//	{
//		cout << e << ' ';
//	}
//	cout << endl;
//
//	return 0;
//}


